Costa bắt đầu chơi tennis từ năm tuổi. Đầu tiên anh ấy đã thu hút sự chú ý của thế giới quần vợt như một cầu thủ đàn em xuất sắc. Năm 1993, anh lọt vào trận chung kết Pháp mở rộng và giành giải Orange Bowl. Anh ấy đã trở nên chuyên nghiệp vào cuối năm đó và nhanh chóng tạo dựng được danh tiếng như một cầu thủ sân đất nện mạnh mẽ. Cựu cầu thủ và bình luận viên người Tây Ban Nha cho truyền hình Tây Ban Nha Andrés Gimeno thường gọi anh là "người đàn ông có hai cú thuận tay", bởi vì anh ta có thể đánh với độ chính xác và sức mạnh tương tự cả thuận tay và trái tay. Năm 1994, anh đã giành được hai sự kiện loạt thử thách và được đặt tên là Người mới đến của ATP.

Costa đã giành được danh hiệu đĩa đơn cấp cao đầu tiên vào năm 1995 tại Kitzbühel, sau khi đánh bại "Vua đất nện", Thomas Muster, trong một trận chung kết năm set, và đó là trận thua đầu tiên của Muster trong 2 trận thua vào năm 1995. Costa đã chấm dứt chuỗi 40 trận thắng liên tiếp của Muster và 11 trận thắng cuối cùng liên tiếp của anh. Costa giành thêm ba danh hiệu vào năm 1996. Năm 1997, anh đã giành được hai danh hiệu đơn khác và là một phần của đội Tây Ban Nha đã giành World Team Cup. Anh đã giành được hai danh hiệu đơn khác vào năm 1998, bao gồm sự kiện Tennis Masters Series ở Hamburg và chơi ở cấp độ tuyệt vời tại Pháp mở rộng, chỉ có một Marcelo Rios xuất sắc có thể ngăn anh ở vòng bốn, nhưng anh đã thiết lập cơ sở cho chiến thắng trong tương lai của mình vào năm 2002. Anh có được ba danh hiệu tiếp theo trong năm 1999.

Năm 2000, Costa đã giúp Tây Ban Nha giành được Cup Davis đầu tiên. Mặc dù bị loại ở vòng đầu tiên ở nội dung đơn nam, anh cũng đã giành được huy chương đồng ở nội dung đôi nam tại Thế vận hội Olympic 2000 ở Sydney, đánh cùng với Álex Corretja.

Bước vào giải Pháp mở rộng năm 2002, Costa đã không giành được một danh hiệu nào kể từ năm 1999 và không được coi là một trong những tay vợt có khả năng vô địch. Là hạt giống thứ 20, anh đánh bại Richard Gasquet, Nikolay Davydenko và Andrea Gaudenzi để lọt vào vòng 4, nơi anh đánh bại hai lần vô địch đương kim vô địch và cựu số 1 thế giới Gustavo Kuerten trong ba set. Anh tiếp tục với chiến thắng năm set trước Guillermo Cañas của Argentina ở tứ kết. Sau đó, anh đánh bại người đồng hương Tây Ban Nha, cựu số 2 thế giới và người bạn lâu năm Àlex Corretja trong trận bán kết bốn set. Trong trận chung kết, Costa đã đối đầu với một người Tây Ban Nha khác, số 1 thế giới tương lai, Juan Carlos Ferrero. Ferrero đã có phong độ tốt trong thời gian sắp tới sự kiện và hầu hết các nhà quan sát đều coi anh là người được đánh giá cao hơn trong trận chung kết. Nhưng Costa đã thắng sau bốn set, 6-1, 6-0, 4-6, 6-3, để giành danh hiệu Grand Slam đầu tiên của mình. Costa đã hủy diệt Ferrero, người chỉ có thể giành được chín điểm trong các game giao bóng của Costa trong 2 set đầu tiên. Chiến thắng đã đẩy anh lên thứ hạng chuyên nghiệp đánh đơn thứ 6 thế giới vào tháng 7/2002.

Đến với Pháp mở rộng 2003 với tư cách là đương kim vô địch, Costa đã dành tổng cộng 21 giờ và 15 phút trên sân, giành bốn chiến thắng trước khi bị Ferrero (người sau đó vô địch) loại ở bán kết.